package q462_minMoves2;

import java.util.Arrays;

public class Solution {
    /*
    此题实际上通过绘图很容易理解 对于一个数组使所有数组元素相等需要的最少移动数
    假设我们有 1 10 2 9 排序后排列在数轴上
    1 2    9 10 显然 只要数字落在2 - 9 之内都是相同的
    所以我们只要排序后找出中间位置的数 然后遍历计算步数即可

    * 优化后的方法 sort的排序时间复杂是nlogn 用快排可以优化到n
     */
    public int minMoves2(int[] nums) {
        Arrays.sort(nums);
        int mid = nums[nums.length / 2];
        int step = 0;
        for (int i = 0; i < nums.length; i++) {
            step += Math.abs(nums[i] - mid);
        }
        return step;
    }
}
